"""
https://leetcode.cn/problems/basic-calculator-ii/description/

227. 基本计算器 II
已解答
中等
相关标签
premium lock icon
相关企业
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

 

示例 1：

输入：s = "3+2*2"
输出：7
示例 2：

输入：s = " 3/2 "
输出：1
示例 3：

输入：s = " 3+5 / 2 "
输出：5
 

提示：

1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

"""

from typing import List


class Solution:
    """
    考虑步骤：
    1. 因子拆分。将数字、算符拆分成数组，并去除空格影响。
    2. 通过栈记录符号和数字，并根据优先级计算
    """

    def calculate(self, s: str) -> int:
        def calc_symbol_priority(s:str)->int:
            if s=='*' or s=='/':
                return 2
            elif s=='+' or s=='-':
                return 1
            else:
                return 0
            
        def calc_val(symbol:str,num2:int,num1:int)->int:
            if symbol=='+':
                return num1+num2
            if symbol=='-':
                return num1-num2
            if symbol=='*':
                return num1*num2
            if symbol=='/':
                return num1//num2

        # 拆分列表
        num_stack:List[any]=[]
        lis:List[any]=[]
        for c in s:
            # 数字处理
            is_num='0'<=c<='9'
            if is_num:
                num_stack.append(c)
                continue
            elif num_stack:
                lis.append(int(''.join(num_stack)))
                num_stack=[]
            # 其他字符处理
            if c!=' ':
                lis.append(c)
        if num_stack:
            lis.append(int(''.join(num_stack)))
            num_stack=[]
        # print(lis)
        
        # 公式计算
        symbol_stack=[]
        for ele in lis:
            priority=calc_symbol_priority(ele)
            if priority==0:
                num_stack.append(ele)
                continue

            while symbol_stack and priority<=calc_symbol_priority(symbol_stack[-1]):
                res=calc_val(symbol_stack.pop(),num_stack.pop(),num_stack.pop())
                # print(res)
                num_stack.append(res)
            symbol_stack.append(ele)
        
        while symbol_stack:
            res=calc_val(symbol_stack.pop(),num_stack.pop(),num_stack.pop())
            # print(res)
            num_stack.append(res)
        
        return num_stack[0]
        pass

if __name__=='__main__':
    # s='123'
    # for i,c in enumerate(s):
    #     print(f'{i},{c}')
    # print('a'<'b')

    s="1*2-3/4+5*6-7*8+9/10"

    sol=Solution()
    res=sol.calculate(s)
    print(res)

